package cn.ly.array.ord;

public class OrdArray {
	
	public long[] a;
	private int nElems;//最后一个元素的位置
	
	public OrdArray(int size){
		a = new long[size];
		this.nElems = 0;
	}
	
	public int getSize(){
		return this.nElems;
	}
	
	//插入
	public void insert(long value){
		int j=0;
		for(; j < this.nElems; j++){
			if(a[j] > value){
				break;
			}
		}
		for(int k = this.nElems; k > j; k--){
			a[k] = a[k-1];
		}
		a[j] = value;
		this.nElems++;
	}
	
	//二分查找插入
	public void insertByHalfFind(long value){
		int index = recursionHalfFind(value, 0, this.nElems-1);
		for(int k = this.nElems; k > index; k--){
			a[k] = a[k-1];
		}
		a[index] = value;
		this.nElems++;
	}
	
	//删除
	public boolean delete(long value){
		int j = halfFind(value);
		if(j == this.nElems){
			return false;
		}else{
			for(; j < this.nElems; j++){
				a[j] = a[j+1];
			}
			this.nElems--;
			return true;
		}
		
	}

	
	//显示
	public void display(){
		for(int j = 0; j < nElems; j++){
			System.out.print(a[j] + " ");
		}
	}
	
	//二分查找，循环法
	private int halfFind(long searchKey){
		int lowerBound = 0;
		int upperBound = this.nElems-1;
		int curIn;
		while(true){
			curIn = (lowerBound + upperBound)/2;
			if(a[curIn] == searchKey){
				return curIn;
			}else if(lowerBound > upperBound){
				return this.nElems;
			}else{
				if(a[curIn] < searchKey){//前面的值都小，需要在后面的部分查找
					lowerBound = curIn + 1;
				}else{
					upperBound = curIn - 1;
				}
			}
		}
	}
	
	//递归二分查找
	private int recursionHalfFind(long searchKey,int start,int end){
		int curIn = (start + end)/2;
		if(a[curIn] >= searchKey && a[curIn-1] < searchKey){
			return curIn;
		}else if(start > end){
			return this.nElems;
		}else{
			if(a[curIn] < searchKey){
				start = curIn + 1;
			}else{
				end = curIn - 1;
			}
			return recursionHalfFind(searchKey,start,end);
		}
		
	}
	
}
